The invention relates to the technical field of cryptography, and more precisely to what is called public key cryptography. In this type of cryptography, a user owns a pair of keys for a given use. Said pair of keys consists of a private key that this user keeps secret and an associated public key that this user may communicate to other users. For example, in the case of a pair of keys dedicated to confidentiality, the public key is then used to encipher the data, whereas the secret key is used to decipher it, that is to say to re-establish this data in clear.
Public key cryptography is very widely used insofar as, unlike secret key cryptography, it does not require the interlocutors to share the same secret in order to establish a security-protected communication. However, this advantage in terms of security is accompanied by a disadvantage in terms of performance, since public key cryptography methods, also called “public key schemes”, are often one hundred or one thousand times slower than secret key cryptography methods, also called “secret key schemes”. A very great challenge is therefore to find public key cryptography methods that can be rapidly executed so as to be able to use them in resource-limited environments, such as standard microprocessor cards, with or without contacts.
Most public key schemes existing at the present time rely on the difficulty of mathematical problems in the field of arithmetic (or “number theory”). Thus, the security of the RSA (Rivest, Shamir, Adleman) numerical signature and encryption scheme is based on the difficulty of the problem of factorizing integers: given a very large integer (having more than 500 digits) obtained privately by multiplying together two or more prime numbers of comparable size, no effective method exists at the present time for recovering these prime numbers.
Other public key schemes, such as the digital signature scheme described in patent application FR-A-2 716 058, rely for their security on the difficulty of what is called the “discrete logarithm problem”. This problem may be expressed in its most general case as follows: let E be a set provided with an operation (i.e. with a function which, having two elements a and b, associates an element denoted “a·b” or “ab”, and called the “product of a and b”), let g be an element of E, let r be a large integer and let y be the integer defined by: y=gr (that is to say the product g·g· . . . ·g, with g occurring r times); it is then unfeasible to recover r from g and y. Often the set E used is the set of integers modulo n, where n is an integer, a prime number or a number composed of prime numbers.
The invention relates more particularly to the technical field of entity authentication, also called “identification”, and also that of the authentication of a message and of its digital signature by means of public key cryptographic techniques. In such methods, the authenticated entity, called the “prover”, possesses a secret or private key and an associated public key. The prover uses the secret key to produce an authentication value or a digital signature. The authenticating entity, called the “verifier”, needs only the public key of the prover to verify the authentication value or the digital signature.
The field of the invention is more particularly still that of the so-called “zero-knowledge” authentication methods. This means that the authentication takes place using a protocol which, in a proven manner, reveals nothing about the secret key of the authenticated entity, irrespective of the number of times it is used. From this type of scheme it is known how to deduce, using standard techniques, schemes for authenticating a message and a digital signature of this message.
The field of the invention is more particularly still that of methods whose security relies both on the difficulty of the problem of factorizing integers and on the difficulty of the discrete logarithm problem.
The invention is applicable in any system using public key cryptography to protect the security of their elements and/or their transactions, and more particularly in systems in which the number of calculations performed by the various parties constitutes, at least for one of them, a critical parameter, either because it does not have available a coprocessor specialized in cryptographic calculations, often called a “cryptoprocessor”, so as to speed up the calculations, or because it is capable of carrying out a large number of calculations simultaneously, for example in the case of central server, or for any other reason.
A typical application is electronic payment, by bank card or by electronic purse. In the case of proximity payment, the payment terminal is in a public place, prompting the use of public key cryptography methods, so as not to store a master key. To reduce the overall costs of such a system, it may be desirable either for the card to be a standard microprocessor card, that is to say a card not provided with a cryptoprocessor, or for the security-protected microprocessor contained in the terminal itself to be of standard type, or for both of these. Depending on the case and on the cryptographic method adopted, the prior art known at the present time does achieve one or other of these objectives, but does not allow both to be easily achieved simultaneously, while complying with the constraints of the system. An example of such a constraint is that the payment shall be effected in less than one second, or even in less than 150 milliseconds in the case of a contactless transaction, or even in a few milliseconds in the case of a freeway toll.
The cryptographic method most widely used at the present time is the RSA method. It is based on the problem of factorization. This algorithm, standardized in various instances, has become a de facto standard. It will remain the predominant algorithm in years to come. Many products, systems and infrastructures, such as PKI (Public Key Infrastructure) infrastructures, have been designed from this algorithm and from the formats of the keys that it uses.
As is known, according to this algorithm the public key consists of a pair of integers (n,e) and the private key consists of an integer d. The modulus n is an integer large enough for it to be unfeasible to factorize it. An entity A which, alone, holds the private key d, is the sole entity capable of generating an integer W′ equal to a power of the integer W modulo n with d as exponent, so as to allow any entity B knowing the public key (n,e) to recover the integer W by raising the integer W′ to a power modulo n with e as exponent.
In a method using a message signature M, the integer W is generally an image of the message via a function such as a known hash function. The prover is the entity A, the signature is the integer W′, the verifier is the entity B which verifies that the integer found, based on the signature W′, is the image of the message via the known function.
In a method of identification, the integer W generally constitutes a challenge sent by the entity B, which is the verifier. The number W′ generated by the entity A, which is the prover, constitutes the response to this challenge.
In a method of authenticating the message M, the integer W generally results from a combination of an image of the message M and of a challenge sent by the verifier consisting of the entity B. The number W′ generated by the entity A, which is the prover, constitutes an authentic signature in response to this challenge.
However, the RSA algorithm has a problem stemming from the large number of operations to be carried out by the prover or the signer. To carry out a complete calculation in less than one second on a microprocessor card performing these operations, it is necessary to add a cryptoprocessor to the card. However, the fabrication and installation of a cryptoprocessor have a not inconsiderable cost, which increases the cost of the microprocessor card. It is also known that a cryptoprocessor consumes a large amount of current. Supplying the card via the terminal may pose technical difficulties in the case of a contactless interface. It is also known that the addition of a cryptoprocessor facilitates physical attack by spectral analysis of the current consumed, which presents a drawback to which it is difficult to find technical solutions. Moreover, even if the card is provided with a cryptoprocessor, the calculation may still prove too slow in applications in which the transaction time needs to be very short, as in certain of the examples mentioned above.
The object of the present invention is to specify public key cryptographic methods such as authentication and digital signature methods. More precisely, the object of the present invention is to use the same keys as the RSA algorithm with a level of security at least equal to that of this algorithm, while still allowing a large majority of the calculations to be carried out in advance, which avoids having to use a cryptoprocessor.